package com.gzq.leet;

public class No5LongestPalindrome {

    //不能处理“aaaa”的情况。仅通过最中心的3个元素不足以确定正确的中心，思路错误引以为鉴
    public String s1_bug(String in_str){
        if(in_str.length()<2){
            return in_str;
        }
        int final_left=0,final_right=0,maxLen=0;
        for(int i=0;i<in_str.length()-1;i++){
            int left=i;
            int right=i+1;
            //确定中心
            char c1=in_str.charAt(left);
            char c2=in_str.charAt(right);

            if(c1==c2){
                if(left>0){
                    char c3=in_str.charAt(left-1);
                    if(c3==c1){//i为中心
                        right--;
                    }else{//i和i+1为中心

                    }
                }else {//i和i+1为中心 但是到头了

                }
            }else{//i为中心
                right--;
            }

            while(left>0 && right<in_str.length()-1){
                c1=in_str.charAt(left-1);
                c2=in_str.charAt(right+1);
                if(c1==c2){
                    left--;
                    right++;
                }else{
                    break;
                }
            }

            int t_len=right-left;
            if(t_len>maxLen){
                final_left=left;
                final_right=right;
                maxLen=t_len;
            }
        }
        //System.out.println("final_left:"+final_left+" final_right:"+final_right);
        return in_str.substring(final_left,final_right+1);
    }

    //暴力解。虽然暴力，但leetcode测试后速度还凑合，没有使用过多内存。
    public String s1(String in_str){
        if(in_str.length()<2){
            return in_str;
        }
        //双中心
        int left,right;
        int final_left=0,final_right=0,maxLen=0,t_len;
        for(int i=0;i<in_str.length()-1;i++){
            left = i;
            right = i;
            if (in_str.charAt(left)==in_str.charAt(right+1)){
                right++;
                while(left>0 && right<in_str.length()-1){
                    if(in_str.charAt(left-1)==in_str.charAt(right+1)){
                        left--;
                        right++;
                    }else{
                        break;
                    }
                }
            }
            t_len=right-left;
            if(t_len>maxLen){
                final_left=left;
                final_right=right;
                maxLen=t_len;
            }

            //单中心
            left = i;
            right = i;
            if(left>0 && in_str.charAt(left-1)==in_str.charAt(right+1)){
                while(left>0 && right<in_str.length()-1){
                    if(in_str.charAt(left-1)==in_str.charAt(right+1)){
                        left--;
                        right++;
                    }else{
                        break;
                    }
                }
            }
            t_len=right-left;
            if(t_len>maxLen){
                final_left=left;
                final_right=right;
                maxLen=t_len;
            }
        }
        return in_str.substring(final_left,final_right+1);
    }


    //动态规划法
    //根据性质：回文串对称去掉两边的字符，子串依然是回文串
    //用2维数组缓存所有结果，从最短的子串开始，枚举判断每种长度的子串是否都是回文
    //比之前的暴力解简短一点，但是leetcode测试后速度比较慢
    public String s2(String in_str){
        if(in_str.length()<2){
            return in_str;
        }
        int len=in_str.length();
        boolean[][] checkedBox = new boolean[len][len];
        for(int k=0;k<len;k++){
            checkedBox[k][k]=true;
        }
        int maxLen=1,final_left=0;
        for(int L=2;L<=len;L++){
            for(int i=0;i<=len-L;i++){
                int j=i+L-1;
                if(in_str.charAt(i)==in_str.charAt(j)){
                    if(j-i>2){
                        checkedBox[i][j]=checkedBox[i+1][j-1];
                    }else{
                        checkedBox[i][j]=true;
                    }
                }else{
                    checkedBox[i][j]=false;
                }
                if(checkedBox[i][j] && L>maxLen){
                    maxLen=L;
                    final_left=i;
                }
            }
        }
        return in_str.substring(final_left,final_left+maxLen);
    }


}
